\documentclass[11pt,letterpaper]{article}

\newcommand{\mytitle}{CS254 Homework 3}
\newcommand{\myauthor}{Kevin Lewi}
\date{February 3, 2012}

\usepackage{hwformat}

\begin{document}

\maketitle

\section*{Problem 1}

We will use the definition of BPP that for a problem in BPP, it is such that 
Yes-instance will be accepted with probability at least $2/3$ and a No-instance 
with probability at most $1/3$.

We construct a circuit $C$ with inputs corresponding to the string of randomness 
bits used by the problem, whose length is at most polynomial in the size of the 
input. The circuit is wired such that the behavior of the algorithm on the 
specific instance is representative of whether or not the circuit accepts.

Thus, one can just run the deterministic algorithm $A$ to see approximately how 
many random strings cause the input to be accepted. If the number $a$ is within 
$0.1$ of $2/3$, then we output that it is a Yes-instance. Otherwise, the number 
$a$ will be within $0.1$ of $1/3$, and we will output that it is a No-instance.

This algorithm is deterministic and so $P = BPP$.

\section*{Problem 2}

Suppose we could show that the hint is true, given the deterministic algorithm 
$A$. Then, we could simply use a binary search process on the parameter $t$ to 
find the appropriate $a$ such that \[ a - \epsilon \leq \pr[C(x) = 1] \leq a + 
\epsilon. \] Basically, if $Z(t,C) = 1$, then you increase $t$ and try again, 
and if $Z(t,C) = 0$, then you decrease $t$ and try again. You have to stop once 
the algorithm $Z(t,C)$ stops giving you an output.

So, I think, to show that the hint is true, you can modify your circuit and 
force some of the inputs to be false or true. Or, perhaps compose multiple 
instances of the circuit into one. This will allow you to narrow down the exact 
number of satisfying assignments to the circuit, which you can toggle for 
increased precision as a function of something polynomial in $1/\epsilon$.



\end{document}
